/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/number-of-1-bits
   @Language: C++
   @Datetime: 20-01-06 10:34
   */

// Method 1, bit manipulation
class Solution {
public:
	int hammingWeight(uint32_t n) {
		int k=0;
		for(k=0; n; n=n&(n-1), ++k);
		return k;
	}
};

// Method 2, search table
class Solution {
public:
	int hammingWeight(uint32_t n) {
		int k=0, bits[]={0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
		for(k=0; n; k+=bits[n&0xF], n>>=4);
		return k;
	}
};
